#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;

int Dijkstra(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;

	for(int i=0;i<n-1;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[t]>dist[j])){
				t=j;
			}
		}
		for(int j=1;j<=n;j++){
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}
	return dist[n];
}

int main(){
	memset(g,0x3f,sizeof g);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
	g[y][x]=g[x][y]=min(g[x][y],z);
	}
	cout<<Dijkstra();
	return 0;
}
